package sol.leetcode;

import java.util.*;

/**
 * Permutations
 */
public class Issue046 {
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> ns = new ArrayList<Integer>();
        List<Integer> px = new ArrayList<Integer>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int num : nums)
            ns.add(num);
        permute(ns, px, res);
        return res;
    }

    private void permute(List<Integer> nums, List<Integer> prefix, List<List<Integer>> res) {
        if (nums.size() == 0)
            res.add(prefix);

        for (Integer num : nums) {
            List<Integer> ns = new ArrayList<Integer>(nums);
            List<Integer> px = new ArrayList<Integer>(prefix);

            px.add(num);
            ns.remove(num);

            permute(ns, px, res);
        }
    }

    public static void main(String[] args) {
        int[] nums = {};
        List<List<Integer>> res = new Issue046().permute(nums);
        for (List<Integer> re : res)
            System.out.println(re);
    }
}
